{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "dog\n",
      "3\n",
      "False\n",
      "8.4\n",
      "True\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "栈：\n",
    "    添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。\n",
    "\n",
    "先进后出\n",
    "\n",
    "可以用线性表、链表实现。\n",
    "\n",
    "栈对于设计计算解析表达式算法非常有用。\n",
    "栈可以提供反转特性。\n",
    "\n",
    "'''\n",
    "\n",
    "class Stack(object):\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        \"\"\" 测试栈是否为空。不需要参数，并返回布尔值。\"\"\"\n",
    "        return self.items == []\n",
    "    \n",
    "    def push(self,item):\n",
    "        \"\"\"将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。\"\"\"\n",
    "        return self.items.append(item)\n",
    "    \n",
    "    def pop(self):\n",
    "        \"\"\"从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。\"\"\"\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def peek(self):\n",
    "        \"\"\"从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。\"\"\"\n",
    "        return self.items[self.size() - 1]\n",
    "    \n",
    "    def size(self):\n",
    "        \"\"\"返回栈中的 item 数量。不需要参数，并返回一个整数。\"\"\"\n",
    "        return len(self.items)\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    s=Stack()\n",
    "    print(s.isEmpty()) # True\n",
    "    s.push(4)\n",
    "    s.push('dog')\n",
    "    print(s.peek()) # dog\n",
    "    s.push(True)\n",
    "    print(s.size()) # 3\n",
    "    print(s.isEmpty()) # False\n",
    "    s.push(8.4)\n",
    "    print(s.pop()) # 8.4\n",
    "    print(s.pop()) # True\n",
    "    print(s.size()) # 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "True\n",
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "\"\"\" \n",
    "用Stack解决括号表达式\n",
    "\"\"\"\n",
    "\n",
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    for i in symbolString:\n",
    "        if i is \"(\":\n",
    "            s.push(i)\n",
    "        elif i is \")\":\n",
    "            if s.isEmpty():\n",
    "                return False\n",
    "            s.pop()\n",
    "    if s.size() is 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(parChecker('((()))'))\n",
    "    print(parChecker('((())(()))'))\n",
    "    print(parChecker('(()'))\n",
    "    print(parChecker(''))\n",
    "    print(parChecker('('))\n",
    "    print(parChecker(')'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "\"\"\" \n",
    "用Stack解决符号匹配\n",
    "{ { ( [ ] [ ] ) } ( ) }\n",
    "[ [ { { ( ( ) ) } } ] ]\n",
    "[ ] [ ] [ ] ( ) { }\n",
    "\n",
    "方括号 [] 用于列表\n",
    "花括号 {} 用于字典\n",
    "括号 () 用于元组和算术表达式\n",
    "\"\"\"\n",
    "def match(b,e):\n",
    "    bs = \"({[\"\n",
    "    es = \")}]\"\n",
    "    return bs.index(b) == es.index(e)\n",
    "\n",
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    for i in symbolString:\n",
    "        if i in \"({[\":\n",
    "            s.push(i)\n",
    "        elif i in \")]}\":\n",
    "            if s.isEmpty() or not match(s.pop(),i):\n",
    "                return False\n",
    "    if s.size() is 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(parChecker(''))\n",
    "    print(parChecker('([][])'))\n",
    "    print(parChecker('{{([][])}()}'))\n",
    "    print(parChecker('[{()]'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "101010\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "十进制转二进制\n",
    "\n",
    "    “除 2”算法，它用栈来跟踪二进制结果的数字。\n",
    "    用栈来记录除以2的余数\n",
    "    \n",
    "    1×2^7 + 1×2^6 + 1×2^5 + 0×2^4 + 1×2^3 + 0×2^2 + 0×2^1 + 1×2^0\n",
    "    11101001\n",
    "    \n",
    "\"\"\"\n",
    "def divideBy2(decNumber, base):\n",
    "    remstack = Stack()\n",
    "    while decNumber > 0:\n",
    "        # 把余数入栈\n",
    "        rem = decNumber % 2\n",
    "        remstack.push(rem)\n",
    "        # 取除以2的整数\n",
    "        decNumber = decNumber // 2\n",
    "\n",
    "    binString = \"\"\n",
    "    while not remstack.isEmpty():\n",
    "        binString = binString + str(remstack.pop())\n",
    "\n",
    "    return binString\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(divideBy2(42))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100011\n",
      "1F\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "将上面的2进制改成任意进制的\n",
    "\"\"\"\n",
    "def divideByBase(decNumber, base):\n",
    "    remstack = Stack()\n",
    "    # 表示余数\n",
    "    digits = \"0123456789ABCDEF\"\n",
    "    \n",
    "    while decNumber > 0:\n",
    "        # 把余数入栈\n",
    "        rem = decNumber % base\n",
    "        remstack.push(rem)\n",
    "        # 取除以base后的整数\n",
    "        decNumber = decNumber // base\n",
    "\n",
    "    binString = \"\"\n",
    "    while not remstack.isEmpty():\n",
    "        binString = binString + digits[remstack.pop()]\n",
    "\n",
    "    return binString\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(divideByBase(35, 2))\n",
    "    print(divideByBase(31, 16))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n\\n中缀表达式：\\n    A + B * C    操作符+ 和 *在数字中间\\n    \\n前缀表达式：\\n     + A * B C   操作符+ 和 *在数字前面\\n     乘法运算符紧接在操作数 B 和 C 之前，表示 * 优先于 +。然后加法运算符出现在 A 和乘法的结果之前。\\n\\n后缀表达式：\\n     A B C * +   操作符+ 和 *在数字后面\\n     因为 * 紧接在 B 和 C 之后出现，表示 * 具有高优先级，+ 优先级低\\n     \\n如果是(A + B) * C呢？\\n前缀表达式：* + A B C  操作符从右往左，放前面，元素的顺序不变\\n后缀表达式：A B + C *  操作符从左往右，放后面，元素的顺序不变\\n'"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "\n",
    "中缀表达式：\n",
    "    A + B * C    操作符+ 和 *在数字中间\n",
    "    \n",
    "前缀表达式：\n",
    "     + A * B C   操作符+ 和 *在数字前面\n",
    "     乘法运算符紧接在操作数 B 和 C 之前，表示 * 优先于 +。然后加法运算符出现在 A 和乘法的结果之前。\n",
    "\n",
    "后缀表达式：\n",
    "     A B C * +   操作符+ 和 *在数字后面\n",
    "     因为 * 紧接在 B 和 C 之后出现，表示 * 具有高优先级，+ 优先级低\n",
    "     \n",
    "如果是(A + B) * C呢？\n",
    "前缀表达式：* + A B C  操作符从右往左，放前面，元素的顺序不变\n",
    "后缀表达式：A B + C *  操作符从左往右，放后面，元素的顺序不变\n",
    "\"\"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A B + C D + *\n",
      "A B + C *\n",
      "A B C * +\n",
      "A B * C +\n",
      "A B * C + D E * +\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "中缀转后缀\n",
    "\"\"\"\n",
    "def infix2postfix(infix_expr):\n",
    "    # 同一类运算符的优先级，主要是比较 加减和乘除\n",
    "    prior = {}\n",
    "    prior[\"*\"] = 3\n",
    "    prior[\"/\"] = 3\n",
    "    prior[\"+\"] = 2\n",
    "    prior[\"-\"] = 2\n",
    "    \n",
    "    prior[\"(\"] = 1\n",
    "    \n",
    "    op_stack = Stack()\n",
    "    post_list = []\n",
    "    \n",
    "    for i in infix_expr:\n",
    "        if i in \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\" or i in \"0123456789\":\n",
    "            # 操作数加入 post_list\n",
    "            post_list.append(i)\n",
    "        elif i is \"(\":\n",
    "            # 括号的情况\n",
    "            op_stack.push(i)\n",
    "        elif i is \")\":\n",
    "            # 出栈\n",
    "            op = op_stack.pop()\n",
    "            while op != '(':\n",
    "                # 表示当前op是之前入栈的操作符\n",
    "                post_list.append(op)\n",
    "                op = op_stack.pop()\n",
    "        elif i in \"+-*/\":\n",
    "            # 操作符入栈，但是判断是否加入后缀列表\n",
    "            # 注意这里的括号优先级最低，也就是说只比较加减和乘除的优先级\n",
    "            # 如果栈里的优先级比当前操作符的优先级大， 则把栈里的操作符入列表，因为高优先级要先放在后缀列表中\n",
    "            while not op_stack.isEmpty() and prior[op_stack.peek()] >= prior[i]:\n",
    "                  post_list.append(op_stack.pop())\n",
    "            op_stack.push(i)\n",
    "\n",
    "    while not op_stack.isEmpty():\n",
    "        post_list.append(op_stack.pop())\n",
    "        \n",
    "    return \" \".join(post_list)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(infix2postfix(\"( A + B) * (C + D)\")) # 'A B + C D + *'\n",
    "    print(infix2postfix(\"( A + B) * C\")) # 'A B + C *'\n",
    "    print(infix2postfix(\"A + B * C\")) # 'A B C * +'\n",
    "    print(infix2postfix(\"A * B + C\")) # 'A B C * +'\n",
    "    print(infix2postfix(\"(A * B + C) + D * E\")) # 'A B * C + D E * +'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.0\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "计算后缀表达式的值\n",
    "\"\"\"\n",
    "\n",
    "def calc_postfix(postfix_expr):\n",
    "    op_stack = Stack()\n",
    "    for i in postfix_expr:\n",
    "        if i in \"0123456789\":\n",
    "            op_stack.push(int(i))\n",
    "        elif i in \"+-*/\":\n",
    "            second = op_stack.pop()\n",
    "            first = op_stack.pop()\n",
    "            if i is \"+\":\n",
    "                value = first+second\n",
    "            elif i is \"-\":\n",
    "                value = first-second\n",
    "            elif i is \"*\":\n",
    "                value = first*second\n",
    "            elif i is \"/\":\n",
    "                value = first/second\n",
    "            op_stack.push(value)\n",
    "    return op_stack.pop()\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(calc_postfix('7 8 + 3 2 + /'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
